package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。
 * 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 */

public class RestoreIpAddresses {
    class Solution {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        public List<String> restoreIpAddresses(String s) {
            backtracking(s, 0, 0);
            return res;
        }

        private void backtracking(String s, int index, int segement){
            if(index == s.length()){
                if(segement == 4) {
                    res.add(sb.substring(0, sb.length() - 1));
                }
                return;
            }

            for(int i = index; i < s.length(); i++){
                if(checkValue(s.substring(index, i+1))){
                    sb.append(s.substring(index, i+1));
                    sb.append(".");
                    backtracking(s, i+1, segement+1);
                    sb.delete(sb.length() - (i+2-index), sb.length());
                }
            }
        }

        private boolean checkValue(String s){
            try {
                if (s.length() > 1 && s.charAt(0) == '0') {
                    return false;
                }
                int value = Integer.parseInt(s);
                return 0 <= value && value <= 255;
            } catch (Exception e) {
                return false;
            }
        }

    }
}
